package swordoffer.offer10_2;

public class ComeSolution {
    /*
    public int JumpFloorII(int target) {
        if (target <= 1) {
            return 1;
        }
        int[] dp = new int[target + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = 2 * dp[i - 1];
        }
        return dp[target];
    }
    */
    // 优化空间

    // f(n) = f(n - 1) + f(n - 2) + f(n - 3) + ... + f(n - n)
    // f(n - 1) = f(n - 2) + f(n - 3) + ... + f(0)
    // 两式相减得到 f(n) = 2 * f(n - 1) 即当前数f(n) = 前一个数字f(n - 1) * 2
    public int JumpFloorII(int target) {
        int f = 1;
        int Fn = 1;
        for (int i = 2; i <= target; i++) {
            Fn = 2 * f;
            f = Fn;
        }
        return Fn;
    }
}
